MacTech 1 to 12/MacTech-vol-1-12.toast/Source/MacTech® Magazine/Volume 09 - 1993/09.07 Jul 93/Programmers' Challenge/MagicAdd.c

Text File | 1993-05-11 | 11.6 KB | 392 lines | [TEXT/KAHL]

/**********************************************************
 * MagicAdd.c
 *
 * Purpose:
 *    This file contains the function CountMagicAdditions()
 *    which solves the May Programmer's Challenge from
 *    MacTech Magazine.
 *
 *    In the functions, rather than using abc + def = ghj,
 *    the variables are repsented by the following notation:
 *           x  x  x
 *            2  1  0
 *        +  y  y  y
 *            2  1  0
 *       -----------  , i.e. x2 = a, x1 = b, y2 = d, etc.
 *           z  z  z
 *            2  1  0
 *
 *    CountmMagicAdditions() and its supporting function
 *    NFind() calculates the number of equations which satisfy
 *    the problem abc + def = ghj, where a...j represent a
 *    digit from 1...9 and each digit appears only once in
 *    the equation.
 *
 *    The main optimization is a property of the problem
 *    which is, g+h+j = 18. My friend, Paul Fieguth,
 *    developed a proof for this which is given later on.
 *
 *    Several other properties are used in order to reduce
 *    the run time such as:
 *
 *    Only one carry is ever generated - another property
 *    from Paul Fieguth's proof.
 *
 *    Basic limits:
 *    3 <= a+b <= 17 where 1 <= a,b <= 9 and no digit is
 *    used twice
 *
 *    If no carry is generated in the addition then
 *    3 <= a+b <= 9 where 1 <= a,b < 9 and no digit is used
 *    twice
 *
 *    If a carry is generated in the addition then
 *    11 <= a+b <= 17 where 1 < a,b <= 9 and no digit is
 *    used twice
 *
 *    Never divide by 2 when you can shift left by 1.
 *
 *    The function starts by determining valid 'ghj'.
 *    Since g+h+j = 18, it can easily reduce the possible #
 *    of valid sums by only generating g,h,j such that their
 *    sum equals 18.
 *    It starts by iterating through valid values of g which
 *    are from 4 to 9. 3 is excluded since the possible
 *    values of ghj where g=3 are invalid [See proof later
 *    on].
 *    After selecting a g, h & j are selected. The
 *    expression (9-z2) is used to start the selection of
 *    the values of h & j since the max value of either h or
 *    j is 9. Say h == 9, that means g + j = 18 - (h=9) = 9.
 *    So j = 9 - g, which translates into (9-z2) in the z0
 *    for-loop.
 *
 *    A check is made to ensure that no digit appears more
 *    than once in ghj and that g,h,j are within the range
 *    1...9.
 *
 *    The fBitUsed bit-array is updated to reflect
 *    those digits that are being used.
 *
 *    Next, the function selects valid a & d values.
 *    This is simplified once we have a valid ghj since
 *    the values of a & d are restricted by the currently-
 *    selected g. It iterates from the (g-1)/2 to 1 for
 *    values of a. This helps generate a,d,g such that
 *    a<d<g. This method is used frequently.
 *
 *    A check is made to ensure that a isn't being used
 *    in ghj. The function then calculates what d should
 *    be in order to satisfy a + d = g.
 *
 *    If d isn't being used in ghj, and j < 8
 *    (a property of the fact that the tens column didn't
 *    generate a carry, so the ones column must generate
 *    a carry. If the ones column does generate a carry. then
 *    the valid values for j are limited) a call is made
 *    to NFind to determine if the currently selected
 *    digits form the basis of an equation which satisfies
 *    the problem. If it does, then the # of valid solutions
 *    is incremented.
 *
 *    d is then decremented to investigate the case where
 *    a + d + 1 = g, i.e. a carry is generated from the
 *    tens column, (b+e = h, h>10). There are checks
 *    made to ensure that the new d isn't being used in ghj
 *    and that a<d and j > 2 (once again this is a property
 *    of the fact that the tens column did generate a carry
 *    so the ones column didn't generate a carry and the
 *    values of j are therefore restricted once again).
 *    If the checks succeed, a call to NFind is made to
 *    see if the current values of a, d, ghj form the
 *    basis of an equation which satisfies the problem.
 *
 *    For NFind, there are two major cases to handle.
 *    One where the tens column generates a carry and one
 *    where the tens column doesn't generate a carry (which
 *    means that the ones column DOES generate a carry -
 *    the hundreds column can't generate a carry).
 *    The first if-statement in NFind handles initializing
 *    the for-loop start & end parameters. The start and
 *    end parameters are derived from the tables for valid
 *    a + b = c shown later on.
 *
 *    In the for-loops, valid c & f are selected and
 *    checked to see if the digits they correspond to are
 *    already being used. If not, then the second for-loop
 *    is entered to determine valid b & e. Once again
 *    checks to ensure that the digits corresponding to b & e
 *    aren't being used are made. If they aren't then we have
 *    a solution!
 *
 * Owner:
 *    Johnny Lee
 *********************************************************/

/**********************************************************
 *    Proofs & Tables
 *
 *    [Paul Fieguth's proof]
 *
 *    The problem is:
 *    Find all of the correct addition problems of the form:
 *    123 + 456 = 789 using each of 1 through 9 once each in
 *    every solution.
 *
 *    Now, in performing the addition, if a carry is never
 *    generated ...
 *         a+b+c+d+e+f = g+h+j
 *
 *    If one carry is generated, then a value of 10 is
 *    turned into a 1 in the next higher column, e.g.,
 *         a+b+c+d+e+f = g+h+j + 9    (9 = 10 - 1)
 *
 *    In general, we can say
 *         a+b+c+d+e+f = g+h+j + n*9  n = 0,1,2,3,...
 *
 *    Now, the sum of digits from one to 9 is
 *     1 + ... + 9 = 45
 *         Let    x = g+h+j     x integer
 *         i.e.,  x + (x + n*9) = 45
 *         Consider each value of  n  separately:
 *           n=0   x = 45 - x      ->  x = 45/2 not integer
 *           n=1   x = 45 - 9 - x  ->  x = 36/2 = 18
 *           n=2   x = 45 -18 - x  ->  x = 27/2 not integer
 *           n=3   x = 45 -27 - x  ->  x = 18/2 = 9
 *
 *    But n=3 is not possible, since we are adding 3 sets of
 *    digits, and the last (hundreds colunm) cannot generate
 *    a carry.  ie, n <= 2
 *
 *    But by the previous argument, if n<=2, then n=1, and
 *    thus x=18.
 *
 *    Therefore  g+h+j = 18 (1) for all satisfying solutions.
 *    Also, only one carry is ever generated.
 *
 *    [Valid values for g]
 *
 *    If we look at the values that g can take:
 *        g    18-g    h,j
 *        9    9        [1,8],[2,7],[3,6],[4,5],[5,4],[6,3],
 *                        [7,2],[8,1]
 *        8    10        [1,9],[3,7],[4,6],[6,4],[7,3],[9,1]
 *        7    11        [2,9],[3,8],[5,6],[6,5],[8,3],[9,2]
 *        6    12        [3,9],[4,8],[5,7],[7,5],[8,4],[9,3]
 *        5    13        [4,9],[6,7],[7,6],[9,4]
 *        4    14        [5,9],[6,8],[8,6],[9,5]
 *
 *    g can't take take a value less than 3 because the
 *    minimum sum of two single-digit integers is 3, i.e
 *    1+2 - remember we're considering the hundreds column
 *    so g can't be greater than 9.
 *
 *    Now 3 is also invalid because the set of numbers which
 *    satisfy (1) for [h,g] are [6,9], [7,8], [8,7], [9,6].
 *    Now the proof above states that there will be one
 *    carry generated for the given equation.
 *
 *    Now consider each set of [h,j] for g = 3:
 *    h=6, j=9:
 *    if j=9, it can't generate the carry since the
 *    max result of adding two single digit number is
 *    17 (=8+9) (2).
 *
 *    So h=6 must generate the carry. But the only two sums
 *    that could generate a 16, (7+9, 8+8) are invalid since
 *    the former contains a digit which is being used in j
 *    and the latter contains the same two digits.
 *
 *    h=7, j=8:
 *    if j=8, it can't generate the carry due to (2),
 *    Therefore, h=7 must generate the carry. But the only
 *    addition which can generate 17 is 8+9 and 8 is being
 *    used already in j.
 *
 *    h=8, j=7:
 *    if j=7, it can't generate the carry since the two
 *    numbers needed to generate 17 are 8,9, but 8 is being
 *    used in h. Therefore h=8 must generate the carry, but
 *    it can't according to (2).
 *
 *    h=9, j=6:
 *    if j=6, it can't generate the carry since the only
 *    valid addition for this problem which can generate
 *    16 uses 7 & 9, but h has the value 9.
 *    Therefore h=9 must generate the carry, but it can't
 *    according to (2).
 *
 *    [How to ensure a<d<g for a + d = g]
 *
 *    Now since abc + def = def + abc = ghj, where a<d<g, the
 *    problem specifies that only one of abc+def & def+abc
 *    can be counted as a solution.
 *    Therefore, when determining a & d, a only needs to
 *    iterate from 1 to (g-1)/2 because if a >= g/2 then
 *    d <= a otherwise we'd have an overflow of the hundreds
 *    column and the problem doesn't allow that.
 *    We check for solutions with a = 1 ... (g-1)/2, and
 *    all solutions for a<g/2 will have been counted already,
 *    so if d is less than a, the solution will be counted
 *    twice.
 *
 *    [Valid a,b,c for a + b = c]
 *    If a carry is generated by a + b = c, then for
 *    valid c (10<c<18):
 *    c    [a,b] pairs
 *    11    [2,9], [3,8], [4,7], [5,6]
 *    12    [3,9], [4,8], [5,7]
 *    13    [4,9], [5,8], [6,7]
 *    14    [5,9], [6,8]
 *    15    [6,9], [7,8]
 *    16    [7,9]
 *    17    [8,9]
 *
 *    Therefore:
 *    a = (c mod 10)+1...((c mod 10)+9)/2
 *    b = c - a
 *
 *    If no carry is generated by a + b = c, then for
 *    valid c (2<c<10):
 *    c    [a,b] pairs
 *    3    [1,2]
 *    4    [1,3]
 *    5    [1,4], [2,3]
 *    6    [1,5], [2,4]
 *    7    [1,6], [2,5], [3,4]
 *    8    [1,7], [2,6], [3,5]
 *    9    [1,8], [2,7], [3,6], [4,5]
 *
 *    a = 1...(c-1)/2
 *    b = c - a
 *********************************************************/

/* Raise 2 to the power of x */
#define PowerTwo(x) (1<<(x))

/* Determine if digit/bit Y in the word X is set */
#define FIsDigitUsed(x,y) ((x) & PowerTwo(y))

/*    NFind
 *
 *    Purpose:
 *        Finds out if there are any equations which fit the
 *        equation, abc + def = ghj given the parameters
 *        passed in.
 *
 *    Arguments:
 *        fDigitsUsed        buffer where every bit that's set
 *                        represents a digit that's been used.
 *        z0                the one digit of the sum
 *        z1                the tens digit of the sum
 *        fCarryFromTensColumn    if the tens column
 *                                generates a carry.
 *
 *    Returns:
 *        Number of equations which satisfy the problem.
 *        Can be either 4 or 0.
 */
short
NFind(short fDigitsUsed, short z0, short z1,
    short fCarryFromTensColumn)
{
    register short x0;
    register short x1;
    register short y0;
    register short fDigitsUsedT;
    short y1;
    short nStop;
    short nStartX1;
    short nStopX1 = 10;

    if ( fCarryFromTensColumn ) {
        x0 = (z0-1)>>1;
        nStartX1 = z1+1;
        z1 += 10;
        nStop = 0;
    }
    else {
        x0 = (z0+9)>>1;
        --z1;
        nStop = z0;
        z0 += 10;
        nStartX1 = 1;
    }

    for (; x0>nStop; --x0) {
        if (FIsDigitUsed(fDigitsUsed,x0))
            continue;
        y0 = z0 - x0;
        if (FIsDigitUsed(fDigitsUsed, y0))
            continue;
        fDigitsUsedT = fDigitsUsed | PowerTwo(x0) | PowerTwo(y0);
        for (x1 = nStartX1; x1<nStopX1; ++x1) {
            if (FIsDigitUsed(fDigitsUsedT,x1))
                continue;
            y1 = z1 - x1;
            if (FIsDigitUsed(fDigitsUsedT,y1))
                continue;
            if (y1 == x1)
                continue;
            return 4;
        }
    }
    return 0;
}

/*    CountMagicAdditions
 *
 *    Purpose:
 *        Calculates the number of equations which satisfy
 *        the problem abc + def = ghj where a-j represent
 *        a digit 1...9 and each digit appears only once
 *        in the equation.
 *
 *    Returns:
 *        Unsigned short    number of Magic Additions
 */
unsigned short
CountMagicAdditions()
{
    short z0;
    short z1;
    short z2;
    short y2;
    short x2;
    short fDigitsUsed;
    short w;
    short cSolutions = 0;

    for (z2 = 9, w = 18 - z2; z2 > 3; --z2, ++w) {
        for (z0 = (z2<9) ? 9 - z2 : 1; z0<10; ++z0) {
            z1 = w - z0;
            if ((z2 == z0) || (z2 == z1) ||
              (z0 == z1) || (z1<1))
                continue;
            fDigitsUsed = PowerTwo(z2) | PowerTwo(z1) |
              PowerTwo(z0);

            for (x2 = (z2-1)>>1; x2 > 0; --x2) {
                if (FIsDigitUsed(fDigitsUsed,x2))
                    continue;
                y2 = z2 - x2;

                if (!FIsDigitUsed(fDigitsUsed,y2) &&
                  (z0<8)) {
                    cSolutions += NFind(fDigitsUsed |
                      PowerTwo(x2) | PowerTwo(y2), z0,
                      z1, 0);
                }
                --y2;
                if (!FIsDigitUsed(fDigitsUsed,y2) &&
                  (y2 > x2) && (z0 > 2)) {
                    cSolutions += NFind(fDigitsUsed |
                      PowerTwo(x2) | PowerTwo(y2), z0,
                      z1, 1);
                }
            }
        }
    }
    return cSolutions;
}